#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

const int inf = 1<<25;
const int maxn = 1010;
int map[maxn][maxn];
int dist[maxn];
bool visited[maxn];
int n, m;

int spfa(int source, int target)
{
	fill(dist, dist+n, inf);
	deque<int> relaxed;
	relaxed.push_back(source);
	dist[source] = 0;
	visited[source] = true;
	//int sum = 0, tot = 1;
	while (!relaxed.empty()) {
		int x = relaxed.front();
		for (int i = 0; i < n; i++)
			if (map[x][i] != -1 && dist[i] > dist[x] + map[x][i]) {
				dist[i] = map[x][i] + dist[x];
				if (!visited[i]) {
					//small label first(slf)
					if (dist[i] < dist[relaxed.front()])
						relaxed.push_front(i);
					else
						relaxed.push_back(i);
					//sum += dist[i]; tot++;
					visited[i] = true;
				}
			}

		relaxed.pop_front();
		visited[x] = false;
		//large label last optimization not work well
		/*
		tot--; sum -= dist[x];
		if (!relaxed.empty()) {
			int avg = sum/tot;
			while (dist[relaxed.front()] > avg) {
				int u = relaxed.front();
				relaxed.pop_front();
				relaxed.push_back(u);
			}
		}
		*/
	}
	return dist[target];
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> m >> n;
	fill(&map[0][0], &map[n][n], -1);
	for (int i = 0; i < m; i++) {
		int x, y, cost;
		cin >> x >> y >> cost;
		x--; y--;
		if (!(map[x][y] != -1 && map[x][y] < cost))
			map[x][y] = map[y][x] = cost;
	}

	cout << spfa(0, n-1) << endl;
}
